Sliding Window是一種針對處理substring以及subarray的解題方法，可以減少時間複雜度，將O(n2)或O(n3)減至O(n)。
那麼Sliding Window是如何減少時間複雜度的呢?
在處理substring與subarray時，常常會使用巢狀的迴圈去遍歷，但這樣的作法會大幅增加時間複雜度，但是使用Sliding Window可以讓巢狀迴圈簡化成一個迴圈。
Sliding Window顧名思義，就是「一個會滑動的窗戶」。
使用一個pointer作為sliding window的起點，並設定window size的範圍，在每一次跑迴圈的時候，去決定是否移動pointer或是改變window size的大小。
題目: 假設今天要在一陣列中找出陣列中連續三個數的最高總合。
假設陣列如下:
[a b c d e f g h]
第一直覺暴力破解，開始用雙迴圈去算陣列中連續三個數的總和，直到找到最大值。如下面示意，每一次都把陣列中的三個整數加總，再比較每一次的總和中的最高值。
max = 0
[a b c] → sum = A //比較 A 與 max, 若 A 較大則更新max的值
[b c d] → sum = B //比較 B 與 max, 若 B 較大則更新max的值
[c d e] → sum = C //...以此類推...
[d e f] → sum = D
[e f g] → sum = E
[f g h] → sum = F
轉換成code
const getMaxmum= (arr) => {
let maxSum = -Infinity; //記錄最大值
let currSum; //記錄當前的總值
for(leti = 0; i <= arr.length- 3; i++) { //第一層迴圈跑整個陣列
currSum = 0;
for(letj = i; j < i + 3; j++) { //第二層迴圈，遍歷每一次的連續三個數
currSum += arr[j];
}
maxSum = Math.max(maxSum, currSum);
}
return maxSum;
};
若改使用Sliding Window呢?
利用window size = 3取代原本的內層for loop，讓window每一次右移完成window內所有整數加總，但是要如何右移呢?
很簡單，把window內最左側的數減掉，再加入陣列中window右側的整數就可以了。
這樣講可能很模糊，看下面的圖解可能會清楚一些~
// 設定 window size = 3 (也就是需要加總整數的範圍)
// max = 0
// windowSum = 0 (window內所有整數總和)
[a b c] → 第一次先把window裡面的數加總，但不需要用另一個loop去加總接下來的每一組連續數總和，讓sliding window去做這件事就可以了
[b _ d] → window 右移，意思就是把 整數a 丟掉，把 整數d 放進window
[c _ e] → window 右移，把 整數b 丟掉，把 整數e 放進window
[d _ f] → ...以此類推...
[e _ g]
[f _ h]
//在每一次window移動的過程中，只要window size = 3，若 windowSum 比 max 大，則更新 max 值
轉換成code
function getMaxSum(arr)
{
let maxSum = 0; //設定最大值
let windowSum = 0; //window內所有數字的總合
let start = 0;
for (let i = 0; i < arr.length; i++) {
windowSum += arr[i];
if ( i - start + 1=== 3) { //當window size達到3
maxSum = Math.max(maxSum, windowSum); //若windowSum比maxSum大，則更新maxSum
windowSum -= arr[start]; //因完成連續三個數的加總，window必須繼續右移，先將window最左側的數值減掉
start += 1; // window向右側移動
}
}
return maxSum;
}
以上是Sliding Window的重點整理以及範例，實際在解題上的應用還是會有些變化的，不過還是可以把握兩元素:window size(sliding window的大小)、window start(sliding window的起點)，先把這兩者定義出來後，會比較好解題~(哈! 這其實是在提醒我自己啦!)
Reference:
iThome鐵人賽
看影片追技術